package com.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author zhang.xin
 * @Description: TODO(这里描述)
 * @Date 2019/12/30
 */
public class Leetcode95 {

    /**
     * 对于第i个结点，他的二叉搜索树由(i-1)个左左子树和（n-i）个子树构成
     * @param n 整数n
     * @return 二叉搜索树列表
     */
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            List<TreeNode> list = new ArrayList<>();
            return list;
        }


        return generateTree(1, n);
    }

    private List<TreeNode> generateTree(int left, int right) {
        List<TreeNode> returnList = new ArrayList<>();
        if (left > right) {
            returnList.add(null);
            return returnList;
        }

        for (int i = left ; i <= right ; i ++) {
            // 左子树的结点
            List<TreeNode> leftNodes = generateTree(left, i -1);
            // 右子树的结点
            List<TreeNode> rightNodes = generateTree(i+1, right);
            for (TreeNode leftNode : leftNodes) {
                for (TreeNode rightNode : rightNodes) {
                    TreeNode currentRoot = new TreeNode(i);
                    currentRoot.left = leftNode;
                    currentRoot.right = rightNode;
                    returnList.add(currentRoot);
                }
            }
        }
        return returnList;
    }

    public static void main(String[] args) {
        Leetcode95 leet = new Leetcode95();
        List<TreeNode> listNodes = leet.generateTrees(3);
        for (TreeNode node : listNodes) {
            System.out.print(node + " ");

        }
    }

}
